We address the following question: When a randomly chosen regular bipartitemulti--graph is drawn in the plane in the ``standard way'', what is thedistribution of its maximum size planar matching (set of non--crossing disjointedges) and maximum size planar subgraph (set of non--crossing edges which mayshare endpoints)? The problem is a generalization of the Longest IncreasingSequence (LIS) problem (also called Ulam's problem). We present combinatorialidentities which relate the number of r-regular bipartite multi--graphs withmaximum planar matching (maximum planar subgraph) of at most d edges to asigned sum of restricted lattice walks in Z^d, and to the number of pairs ofstandard Young tableaux of the same shape and with a ``descend--type''property. Our results are obtained via generalizations of two combinatorialproofs through which Gessel's identity can be obtained (an identity that iscrucial in the derivation of a bivariate generating function associated to thedistribution of LISs, and key to the analytic attack on Ulam's problem). We also initiate the study of pattern avoidance in bipartite multigraphs andderive a generalized Gessel identity for the number of bipartite 2-regularmultigraphs avoiding a specific (monotone) pattern.
展开▼
